/*-------------------------------------------------------------------------
 *
 * list.c
 *	  implementation for PostgreSQL generic list package
 *
 * See comments in pg_list.h.
 *
 *
 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/nodes/list.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "common/int.h"
#include "my_pg_list.h"
#include "port/pg_bitutils.h"
//#include "utils/memdebug.h"
#include "utils/memutils.h"


/*
 * The previous MyList implementation, since it used a separate palloc chunk
 * for each cons cell, had the property that adding or deleting list cells
 * did not move the storage of other existing cells in the list.  Quite a
 * bit of existing code depended on that, by retaining MyListCell pointers
 * across such operations on a list.  There is no such guarantee in this
 * implementation, so instead we have debugging support that is meant to
 * help flush out now-broken assumptions.  Defining DEBUG_LIST_MEMORY_USAGE
 * while building this file causes the MyList operations to forcibly move
 * all cells in a list whenever a cell is added or deleted.  In combination
 * with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose
 * broken code.  It's a bit expensive though, as there's many more palloc
 * cycles and a lot more data-copying than in a default build.
 *
 * By default, we enable this when building for Valgrind.
 */
#ifdef USE_VALGRIND
#define DEBUG_LIST_MEMORY_USAGE
#endif

/* Overhead for the fixed part of a MyList header, measured in MyListCells */
#define LIST_HEADER_OVERHEAD  \
	((int) ((offsetof(MyList, initial_elements) - 1) / sizeof(MyListCell) + 1))

/*
 * Macros to simplify writing assertions about the type of a list; a
 * NIL list is considered to be an empty list of any type.
 */
//#define IsPointerList(l)		((l) == MYNIL || IsA((l), MyList))

#ifdef USE_ASSERT_CHECKING
/*
 * Check that the specified MyList is valid (so far as we can tell).
 */
static void
check_list_invariants(const MyList *list)
{
	if (list == MYNIL)
		return;

	Assert(list->length > 0);
	Assert(list->length <= list->max_length);
	Assert(list->elements != NULL);

	Assert(list->type == T_List);
}
#else
#define check_list_invariants(l)  ((void) 0)
#endif							/* USE_ASSERT_CHECKING */

/*
 * pg_nextpower2_32
 *      Returns the next higher power of 2 above 'num', or 'num' if it's
 *     already a power of 2.
 *
 * 'num' mustn't be 0 or be above PG_UINT32_MAX / 2 + 1.
 */
static inline uint32
pg_nextpower2_32(uint32 num)
{
    Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);

    /*
 *   * A power 2 number has only 1 bit set.  Subtracting 1 from such a number
 *       * will turn on all previous bits resulting in no common bits being set
 *           * between num and num-1.
 *               */
    if ((num & (num - 1)) == 0)
        return num;             /* already power 2 */

    return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
}

/*
 * Return a freshly allocated MyList with room for at least min_size cells.
 *
 * Since empty non-NIL lists are invalid, new_list() sets the initial length
 * to min_size, effectively marking that number of cells as valid; the caller
 * is responsible for filling in their data.
 */
static MyList *
my_new_list(NodeTag type, int min_size)
{
	MyList	   *newlist;
	int			max_size;

	Assert(min_size > 0);

	/*
	 * We allocate all the requested cells, and possibly some more, as part of
	 * the same palloc request as the MyList header.  This is a big win for the
	 * typical case of short fixed-length lists.  It can lose if we allocate a
	 * moderately long list and then it gets extended; we'll be wasting more
	 * initial_elements[] space than if we'd made the header small.  However,
	 * rounding up the request as we do in the normal code path provides some
	 * defense against small extensions.
	 */

#ifndef DEBUG_LIST_MEMORY_USAGE

	/*
	 * Normally, we set up a list with some extra cells, to allow it to grow
	 * without a repalloc.  Prefer cell counts chosen to make the total
	 * allocation a power-of-2, since palloc would round it up to that anyway.
	 * (That stops being true for very large allocations, but very long lists
	 * are infrequent, so it doesn't seem worth special logic for such cases.)
	 *
	 * The minimum allocation is 8 MyListCell units, providing either 4 or 5
	 * available MyListCells depending on the machine's word width.  Counting
	 * palloc's overhead, this uses the same amount of space as a one-cell
	 * list did in the old implementation, and less space for any longer list.
	 *
	 * We needn't worry about integer overflow; no caller passes min_size
	 * that's more than twice the size of an existing list, so the size limits
	 * within palloc will ensure that we don't overflow here.
	 */
	max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
	max_size -= LIST_HEADER_OVERHEAD;
#else

	/*
	 * For debugging, don't allow any extra space.  This forces any cell
	 * addition to go through enlarge_list() and thus move the existing data.
	 */
	max_size = min_size;
#endif

	newlist = (MyList *) palloc(offsetof(MyList, initial_elements) +
							  max_size * sizeof(MyListCell));
	newlist->type = type;
	newlist->length = min_size;
	newlist->max_length = max_size;
	newlist->elements = newlist->initial_elements;

	return newlist;
}

/*
 * Enlarge an existing non-NIL MyList to have room for at least min_size cells.
 *
 * This does *not* update list->length, as some callers would find that
 * inconvenient.  (list->length had better be the correct number of existing
 * valid cells, though.)
 */
static void
my_enlarge_list(MyList *list, int min_size)
{
	int			new_max_len;

	Assert(min_size > list->max_length);	/* else we shouldn't be here */

#ifndef DEBUG_LIST_MEMORY_USAGE

	/*
	 * As above, we prefer power-of-two total allocations; but here we need
	 * not account for list header overhead.
	 */

	/* clamp the minimum value to 16, a semi-arbitrary small power of 2 */
	new_max_len = pg_nextpower2_32(Max(16, min_size));

#else
	/* As above, don't allocate anything extra */
	new_max_len = min_size;
#endif

	if (list->elements == list->initial_elements)
	{
		/*
		 * Replace original in-line allocation with a separate palloc block.
		 * Ensure it is in the same memory context as the MyList header.  (The
		 * previous MyList implementation did not offer any guarantees about
		 * keeping all list cells in the same context, but it seems reasonable
		 * to create such a guarantee now.)
		 */
		list->elements = (MyListCell *)
			MemoryContextAlloc(GetMemoryChunkContext(list),
							   new_max_len * sizeof(MyListCell));
		memcpy(list->elements, list->initial_elements,
			   list->length * sizeof(MyListCell));

		/*
		 * We must not move the list header, so it's unsafe to try to reclaim
		 * the initial_elements[] space via repalloc.  In debugging builds,
		 * however, we can clear that space and/or mark it inaccessible.
		 * (wipe_mem includes VALGRIND_MAKE_MEM_NOACCESS.)
		 */
#ifdef CLOBBER_FREED_MEMORY
        memset(list->initial_elements, 0x7F, list->max_length * sizeof(MyListCell));
#else
		VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
								   list->max_length * sizeof(MyListCell));
#endif
	}
	else
	{
#ifndef DEBUG_LIST_MEMORY_USAGE
		/* Normally, let repalloc deal with enlargement */
		list->elements = (MyListCell *) repalloc(list->elements,
											   new_max_len * sizeof(MyListCell));
#else
		/*
		 * repalloc() might enlarge the space in-place, which we don't want
		 * for debugging purposes, so forcibly move the data somewhere else.
		 */
		MyListCell   *newelements;

		newelements = (MyListCell *)
			MemoryContextAlloc(GetMemoryChunkContext(list),
							   new_max_len * sizeof(MyListCell));
		memcpy(newelements, list->elements,
			   list->length * sizeof(MyListCell));
		pfree(list->elements);
		list->elements = newelements;
#endif
	}

	list->max_length = new_max_len;
}

/*
 * Convenience functions to construct short Lists from given values.
 * (These are normally invoked via the list_makeN macros.)
 */
MyList *
my_list_make1_impl(NodeTag t, MyListCell datum1)
{
	MyList	   *list = my_new_list(t, 1);

	list->elements[0] = datum1;
	check_list_invariants(list);
	return list;
}

/*
 * Make room for a new tail cell in the given (non-NIL) list.
 *
 * The data in the new tail cell is undefined; the caller should be
 * sure to fill it in
 */
static void
my_new_tail_cell(MyList *list)
{
	/* Enlarge array if necessary */
	if (list->length >= list->max_length)
		my_enlarge_list(list, list->length + 1);
	list->length++;
}

/*
 * Append a pointer to the list. A pointer to the modified list is
 * returned. Note that this function may or may not destructively
 * modify the list; callers should always use this function's return
 * value, rather than continuing to use the pointer passed as the
 * first argument.
 */
MyList *
my_lappend(MyList *list, void *datum)
{
	//Assert(IsPointerList(list));

	if (list == MYNIL)
		list = my_new_list(T_List, 1);
	else
		my_new_tail_cell(list);

	my_llast(list) = datum;
	check_list_invariants(list);
	return list;
}

/*
 * Truncate 'list' to contain no more than 'new_size' elements. This
 * modifies the list in-place! Despite this, callers should use the
 * pointer returned by this function to refer to the newly truncated
 * list -- it may or may not be the same as the pointer that was
 * passed.
 *
 * Note that any cells removed by list_truncate() are NOT pfree'd.
 */
static MyList *
my_list_truncate(MyList *list, int new_size)
{
	if (new_size <= 0)
		return MYNIL;				/* truncate to zero length */

	/* If asked to effectively extend the list, do nothing */
	if (new_size < my_list_length(list))
		list->length = new_size;

	/*
	 * Note: unlike the individual-list-cell deletion functions, we don't move
	 * the list cells to new storage, even in DEBUG_LIST_MEMORY_USAGE mode.
	 * This is because none of them can move in this operation, so just like
	 * in the old cons-cell-based implementation, this function doesn't
	 * invalidate any pointers to cells of the list.  This is also the reason
	 * for not wiping the memory of the deleted cells: the old code didn't
	 * free them either.  Perhaps later we'll tighten this up.
	 */

	return list;
}

/*
 * Free all storage in a list, and optionally the pointed-to elements
 */
static void
my_list_free_private(MyList *list, bool deep)
{
    if (list == MYNIL)
        return;                 /* nothing to do */

    check_list_invariants(list);

    if (deep)
    {
        for (int i = 0; i < list->length; i++)
            pfree(my_lfirst(&list->elements[i]));
    }
    if (list->elements != list->initial_elements)
        pfree(list->elements);
    pfree(list);
}

/*
 * Free all the cells of the list, as well as the list itself. Any
 * objects that are pointed-to by the cells of the list are NOT
 * free'd.
 *
 * On return, the argument to this function has been freed, so the
 * caller would be wise to set it to NIL for safety's sake.
 */
static void
my_list_free(MyList *list)
{
    my_list_free_private(list, false);
}


/*
 * Delete the last element of the list.
 */
MyList *
my_list_delete_last(MyList *list)
{
	check_list_invariants(list);

	if (list == MYNIL)
		return MYNIL;				/* would an error be better? */

	/* list_truncate won't free list if it goes to empty, but this should */
	if (my_list_length(list) <= 1)
	{
		my_list_free(list);
		return MYNIL;
	}

	return my_list_truncate(list, my_list_length(list) - 1);
}


/*
 * Return a shallow copy of the specified list.
 */
MyList *
my_list_copy(const MyList *oldlist)
{
	MyList	   *newlist;

	if (oldlist == MYNIL)
		return MYNIL;

	newlist = my_new_list(oldlist->type, oldlist->length);
	memcpy(newlist->elements, oldlist->elements,
		   newlist->length * sizeof(MyListCell));

	check_list_invariants(newlist);
	return newlist;
}


/*
 * Sort a list according to the specified comparator function.
 *
 * The list is sorted in-place.
 *
 * The comparator function is declared to receive arguments of type
 * const MyListCell *; this allows it to use lfirst() and variants
 * without casting its arguments.  Otherwise it behaves the same as
 * the comparator function for standard qsort().
 *
 * Like qsort(), this provides no guarantees about sort stability
 * for equal keys.
 *
 * This is based on qsort(), so it likewise has O(N log N) runtime.
 */
void
my_list_sort(MyList *list, my_list_sort_comparator cmp)
{
	typedef int (*qsort_comparator) (const void *a, const void *b);
	int			len;

	check_list_invariants(list);

	/* Nothing to do if there's less than two elements */
	len = my_list_length(list);
	if (len > 1)
		qsort(list->elements, len, sizeof(MyListCell), (qsort_comparator) cmp);
}

